class Solution(object):
    def cherryPickup(self, grid):
        m = len(grid)
        n = len(grid[0])
        st = [[-1] * n for _ in range(n)]
        st[0][n - 1] = grid[0][0] + grid[0][n - 1]
        for k in range(1, m):
            next_st = [[-1] * n for _ in range(n)]
            for i in range(n):
                for j in range(n):
                    if st[i][j] >= 0:
                        for ux in range(i - 1, i + 2):
                            for uy in range(j - 1, j + 2):
                                if 0 <= ux < n and 0 <= uy < n:
                                    if ux == uy:
                                        next_st[ux][uy] = max(next_st[ux][uy], st[i][j] + grid[k][ux])
                                    else:
                                        next_st[ux][uy] = max(next_st[ux][uy], st[i][j] + grid[k][uy] + grid[k][ux])
            st = next_st
        return max([max([st[i][j] for j in range(n)]) for i in range(n)])



data = Solution()
grid = [[3, 1, 1], [2, 5, 1], [1, 5, 5], [2, 1, 1]]
print(data.cherryPickup(grid))
